# Definition for a binary tree node.
"""
给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3
"""


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def isSym(l, r):
            if not r and not l: return True
            if not r or not l: return False
            if l.val == r.val:
                return isSym(l.left,r.right) and isSym(l.right, r.left)
            else:
                return False
        if not root: return True
        return isSym(root.left,root.right)

    def isSymmetric1(self, root):
        cur = [root]
        while cur:
            i, j = 0, len(cur)-1
            nextstack = []
            for x in cur:
                if not x or x.val == "#": continue
                if x.left: nextstack.append(x.left)
                else: nextstack.append(TreeNode("#"))
                if x.right: nextstack.append(x.right)
                else: nextstack.append(TreeNode("#"))
            while i < j:
                if cur[i] == "#" : cur[i] = TreeNode("#")
                if cur[j] == "#" : cur[j] = TreeNode("#")
                if cur[i].val != cur[j].val:
                    return False
                else:
                    i += 1
                    j -= 1
            cur = nextstack
        return True

a1 = TreeNode(1)
a2 = TreeNode(2)
a3 = TreeNode(2)
a4 = TreeNode(3)
a5 = TreeNode(3)
a1.left = a2
a1.right = a3
a2.right = a4
a3.right = a5
s = Solution()
print(s.isSymmetric1(a1))
